package org.example.leetCode;

/**
 * 459. 重复的子字符串
 * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
 */
public class Code459 {
    public boolean repeatedSubstringPattern(String s) {
        String ss = s + s;
        char[] p = s.toCharArray();
        char[] str = new char[ss.length() - 2];
        for (int i = 0; i < str.length; i++) {
            str[i] = ss.charAt(i + 1);
        }
        int[] next = getNext(p);
        return kmp(next, str, p);
    }

    private boolean kmp(int[] next, char[] str, char[] p) {
        for (int i = 0, j = 0; i < str.length; i++) {
            while (j > 0 && str[i] != p[j]) {
                j = next[j - 1];
            }
            if (str[i] == p[j]) j++;
            if(j==p.length)return true;
        }
        return false;
    }

    private int[] getNext(char[] p) {
        int[] next = new int[p.length];
        next[0] = 0;
        for (int i = 1, j = 0; i < p.length; i++) {
            while (j > 0 && p[i] != p[j]) j = next[j - 1];
            if (p[i] == p[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
}
